package com.hardy.leecode;

/**
 * Author: Hardy
 * Date:   2020/12/15
 * Description:
 * - 剑指 Offer 51. 数组中的逆序对
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: [7,5,6,4]
 * 输出: 5
 *  
 * <p>
 * 限制：
 * <p>
 * 0 <= 数组长度 <= 50000
 **/
public class QueOffer51 {
    public static void main(String[] args) {

        System.out.println(new Solution().reversePairs(new int[]{7, 5, 6, 4, 5, 4}));
    }

    static class Solution {

        public int reversePairs(int[] nums) {
            if (nums.length <= 1) return 0;
            return merge(0, nums.length - 1, nums, new int[nums.length]);
        }

        public int merge(int l, int r, int[] nums, int[] res) {
            if (l == r) {
                res[0] = nums[l];
                return 0;
            }

            int c = 0;
            int m = (l + r) / 2;

            int[] ls = new int[m - l + 1];
            int[] rs = new int[r - m ];

            c += merge(l, m, nums, ls);
            c += merge(m + 1, r, nums, rs);

            for (int i = 0, j = 0, k = 0; k < res.length; k++) {
                if (i < ls.length) {
                    if (j < rs.length) {
                        if (ls[i] > rs[j]) {
                            res[k] = rs[j++];
                            c += ls.length - i;
                        } else {
                            res[k] = ls[i++];
                        }
                    } else {
                        res[k] = ls[i++];
                    }
                } else {
                    res[k] = rs[j++];
                }
            }
            return c;
        }
    }
}
